Home | | Latest | About | Random
# 04 Gaussian elimination.
Now let us return to the problem of solving system of linear equations. Despite that there are many approaches to take a linear system to an echelon form (so that we can just back-substitute), we can **algorithmically** do it, called **Gaussian elimination**.
Let me describe the procedure in general first. The goal is to produce an echelon form for our linear system, so we can then solve the variables via back-substitutions.
(0) Before we start, write the system in augmented matrix to simplify our life, label the coefficient columns with the corresponding variables so you don't get confused.
Algorithm sketch. Gaussian elimination.
Input $M$.
Output $\text{RREF}(M)$
(1) Swap all the rows that are entirely zeros to the bottom of the matrix. We will work column by column to produce an echelon form. Start with the first column.
(2) Look at the current column, identify a nonzero entry to serve as the pivot of the resulting echelon form.
(2A) If this column is entirely zero, move on to the next column and repeat (2).
(2B) Use elementary row swap to move this pivot and its row upwards as much as you can while maintaining a potential echelon form.
(2C) Use elementary row replacement and use this pivot row to "kill" all the nonzero entries below it in this column. This clears everything below this pivot to be zero.
(2D) Since we established a pivot position already, we should only consider rows below the current pivot from now on. Move on to the next column and repeat (2)
Doing this would yield an echelon form (EF), and for solving system of linear equations, this is often enough. But we can continue to get row echelon form (REF) and reduced row echelon form (RREF).
(3) Now with our echelon form, scale each row appropriately so the pivot is now all $1$'s.
At this step we would have a row echelon form (REF). To continue to get a reduced row echelon form (RREF), we now need to clear entries above each pivot.
(4) Starting with the pivot that furthest right, use it and perform elementary row replacement to clear entries above it and make them zero. Repeat until no more.
And the resulting matrix would be in reduced row echelon form (RREF).
So given a linear system, we can write out its augmented matrix, apply Gaussian elimination (to either EF, REF, RREF, whichever you fancy, for now), and then interpret the answer back.
For example. Let us solve the system $$
\left\{\begin{array}{}
x & + & 2y & + & 3z & = & 1 \\
x & - & y & - & z & = & 2 \\
2x & + & y & + & z & = & 3
\end{array}\right.
$$First we write out its augmented matrix with columns labeled with the corresponding variables: $$
\begin{array}{}
x\ \ \ \ \ \ y \ \ \ \ \ \ z\ \ \ \ \ \ \ \ \ \ \ \ \\
\begin{bmatrix}
\colorbox{lightblue}1 & 2 & 3 & \vdots & 1 \\
1 & -1 & -1 & \vdots & 2 \\
2 & 1 & 1 & \vdots & 3
\end{bmatrix}
\end{array}
$$Using the blue $\colorbox{lightblue} 1$ as a pivot, we apply replacements on row 2 and row 3 to clear everything below this pivot, namely $(R_{2})\to(R_{2})-(R_{1})$ and $(R_{3})\to(R_{3})-2(R_{1})$ : $$
\begin{array}{}
x\ \ \ \ \ \ y \ \ \ \ \ \ z\ \ \ \ \ \ \ \ \ \ \ \ \\
\begin{bmatrix}
\colorbox{lightblue}1 & 2 & 3 & \vdots & 1 \\
0 & \colorbox{lightblue} {$-3$} & -4 & \vdots & 1 \\
0 & -3 & -5 & \vdots & 1
\end{bmatrix}
\end{array}
$$Now we move to the next column, and down one spot (since row 1 already has a pivot), and we use the blue $\colorbox{lightblue} {\(-3\)}$ as a pivot, and apply replacement $(R_{3})\to(R_{3})-(R_{2})$ to clear the entries below: $$
\begin{array}{}
x\ \ \ \ \ \ y \ \ \ \ \ \ z\ \ \ \ \ \ \ \ \ \ \ \ \\
\begin{bmatrix}
\colorbox{lightblue}1 & 2 & 3 & \vdots & 1 \\
0 & \colorbox{lightblue}{$-3$} & -4 & \vdots & 1 \\
0 & 0 & \colorbox{lightblue}{$-1$} & \vdots & 0
\end{bmatrix}
\end{array}
$$And now we achieved an echelon form (EF), which we can already use it to solve the system. If you desire you can continue to obtain its REF or RREF. It is not necessary for now, but later RREF will be useful in other ways.
So what does this mean? This means our original system has the same solutions (as we used elementary row operations that preserve solutions) as this new linear system:$$
\left\{\begin{array}{}
x & + & 2y & + & 3z & = & 1 \\
& & -3y & - & 4z & = & 1 \\
& & & & -z & = & 0
\end{array}\right.
$$ And solving backwards, we have $z = 0$, $y = -1 / 3$, and $x = 5 / 3$.
Remark. If you are patient you can use it to solve much larger systems, you just have to be careful. One can show that this algorithm is essentially as fast as it could get in the most general sense, with a time complexity of about $O(n^{3})$.